/*
 * @lc app=leetcode.cn id=393 lang=cpp
 *
 * [393] UTF-8 编码验证
 */

// @lc code=start
class Solution
{
    int MASK1 = 0x80, MASK2 = 0x80 + 0x40;

public:
    int getBytes(int num)
    {
        if ((num & MASK1) == 0)
        {
            return 1;
        }

        int n = 0;
        int mask = MASK1;
        while ((num & mask) != 0)
        {
            n++;
            if (n > 4)
            {
                return -1;
            }
            mask >>= 1;
        }
        return n < 2 ? -1 : n;
    }

    bool isValid(int num)
    {
        return (num & MASK2) == MASK1;
    }

    bool validUtf8(vector<int> &data)
    {
        int n = data.size();
        int idx = 0;
        while (idx < n)
        {
            int num = data[idx];
            int bytes = getBytes(num);
            if (bytes < 0 || idx + bytes > n)
            {
                return false;
            }
            for (int i = 1; i < bytes; i++)
            {
                if (!isValid(data[idx + i]))
                {
                    return false;
                }
            }
            idx += bytes;
        }
        return true;
    }
};
// @lc code=end
